#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

struct ListNode {
 int val;
 ListNode *next;
 ListNode(int x) : val(x), next(NULL) {}
};

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *ret=l1;
    ListNode *p1=l1;
    ListNode *p2=l2; 
    while(1) {
        p1->val = p1->val + p2->val;
        p2->val = p1->val;
        if(p1->next!=NULL && p2->next!=NULL) {
            p1=p1->next;
            p2=p2->next;
        } else if (p1->next==NULL && p2->next!=NULL) {
            p1->next = p2->next;
            break;
        } else if (p1->next!=NULL && p2->next==NULL) {
            break;
        } else {
            break;
        }
    } 
    int up = 0; 
    ListNode *l=NULL;
    for(l=ret; l->next!=NULL; l=l->next) {  //末尾元素单独处理
        l->val = l->val+up;
        up = 0;
        if(l->val>9){
            up = 1;
            l->val = l->val-10;
        }
    }
    if(1==up || l->val>9) {//末尾元素>9的时候需要单独处理
        l->val = l->val+up;
        if(l->val>9){
            l->val = l->val-10;
            l->next = new ListNode(1);
        }
    }
        
    return ret;
}


int main() {
    ListNode* l1= new ListNode(0);
    ListNode* l2= new ListNode(0);
    ListNode * ret=NULL;
    int a[] = {2,4,5};
    int b[] = {5,6,4};
    int i=0;
    for(ListNode*l=l1; i<3; l=l->next) {
        l->val = a[i++];
        l->next =  new ListNode(0);
        if(i==3)
            l->next = NULL;
    }
    i=0;
    for(ListNode *l=l2; i<3; l=l->next) {
        l->val = b[i++];
        l->next = new ListNode(0);
        if(i==3)
            l->next = NULL;
    }
    ret = addTwoNumbers(l1, l2);
    for(ListNode *l=ret; l!=NULL; l=l->next) {
        cout<<l->val;
    }
    return 0;
}

